#ifndef CTREE_H
#define CTREE_H

#include <map>
#include <utility>
#include <iterator>
#include <iostream>
#include <cmath>
#include <sstream>
#include <fstream>
#include <vector>
#include "CTreeException.h"
#include "CBaseException.h"
#include "SerialException.h"

using namespace exceptions;

namespace treelib
{

template <typename T>
class CTree
{
      typedef std::multimap<T*,T> CContainer;
	  
      

	  
      CContainer tree;
	  template <typename U>
	  friend std::ostream& operator<<(std::ostream& str,const CTree<U> &mtree);

  public: 
	class tree_iterator;

	CTree()
	{
	}

	~CTree()
	{
	}

	void addRoot(T Node)
	 {
	   if (!tree.empty()) 
	   {
			CTreeException noNode(0,"addNode",tree.size(),9);
			throw noNode;
	   }
		tree.insert(make_pair((T*) NULL, Node));
	 }
   
      

     bool addNode(int n, T Node) // добавление потомка к элементу n в дереве. n - это порядковый номер элемента в списке. нумерация начиается с нуля. сортировка идет по адресам.
				// т.к. дерево бинарное проверка того, что не добавляется третий элемент
	 {
		
			if (tree.empty())
			{
				CTreeException noNode(0,"addNode",tree.size(),9);
				throw noNode;
			}

			else
			{

				typename CContainer::iterator s_node;
				s_node=getNodeN(n);
				T* parent=&(s_node->second);
				int i;
			    i = checkParent(Node,*parent);
				tree.insert(make_pair(parent,Node)); 
			}

			return true;

	}  
      
	bool empty()
	{
		return tree.empty();
	}

    int addNode(T* iter, T Node) // добавление по указателю на элемент дерева
	 {
	    
	    if (tree.empty())
			{
				CTreeException noNode(0,"addNode",tree.size(),9);
				throw noNode;
			}
	    int i;
	    
		i = checkParent(Node,*iter);
	    if (i ==0 )tree.insert(make_pair(iter,Node)); 
		else return 2;
	    return 0;
	
	 }
		

	  std::string getNode(int n)
	  {
		typename CContainer::iterator s_node = getNodeN(n);
		std::string strperson = "";
		T person = s_node->second;
		strperson = person.getAll(); //  класс T ДОЛЖЕН иметь метод getAll()
		return strperson;
	  }

	  T* getNodeObj(int n)
	  {
		typename CContainer::iterator s_node = getNodeN(n);
		std::string strperson = "";
		return &(s_node->second);

	  }

     int size() const
	 {
	    return tree.size();
	 }

	int size(int n)
	{
		tree_iterator iter = this->iteratorN(n);
		iter++;
		int i = 1;
		while (iter.getLevel() != 0) 
		{
			iter++;
			i++;
		}

		return i;
	}

	
		      
     void clear()
	{
		tree.clear();
	} 

     int deepTree()
	 {
	    int deep;
		tree_iterator iter = this->begin();
		int _size = tree.size();
		int new_level=0;
		int level=0;
		for (int i=1; i<=_size; i++)
		{
			new_level = iter.getLevel();
			iter++;
			if ( level < new_level) level = new_level;

		}
		deep =  level;
	    return deep+1;
	 } 

      

      tree_iterator begin()
	 {
	    typename CContainer::iterator s_node;
	    
	    s_node = tree.find((T*) NULL);  
	    return tree_iterator(s_node, &tree);
	    
	 }
	  
      tree_iterator iteratorN(int n)
	 {
	    typename CContainer::iterator s_node;
	    
	    s_node = getNodeN(n);
	    return tree_iterator(s_node, &tree);
	    
	 }

	int getLevel(int n)
	{
		tree_iterator it = this->begin();
		typename CContainer::iterator s_node;
	    s_node = getNodeN(n);
		T node = s_node->second;
		
		while (node !=  *it) it++;
		return it.getLevel();


	}

	int delNode(int n)
	{
		int num = this->size(n);
		if  (num >1) 
		{
			CTreeException noNode(3,"delNode",tree.size(),num);
			throw noNode;
		}
			
			tree.erase(getNodeN(n));

	}

     
   private:   
      typename CContainer::iterator getNodeN(int n) // переход к элементу n в multi-map
	 {
	    typename CContainer::iterator s_node;
	    s_node=tree.begin();
		if (tree.size() < n)
		{
			CTreeException noNode(2,"getNodeN",tree.size(),n);
			throw noNode;
		}
	    advance(s_node,n);
	    return s_node;
	 }

   
	  int checkParent(T& Node, T& parent)
		{
		int i=tree.count(&parent);
		if (i==2)  
		{
			CTreeException noNode(1,"checkParent",tree.size(),i);
			throw noNode;
		}
	 	else
			{
				if (i==1) 
					{
						typename CContainer::iterator s_node1;
						s_node1 = tree.find(&parent);
						if (Node.getSex() == s_node1->second.getSex()) 
						{
							CTreeException noNode(1,"checkParent",tree.size(),Node.getSex());
							throw noNode;
						}
					}
			}
	    return 0;
		}

   public:
     class tree_iterator:public std::iterator<std::bidirectional_iterator_tag, T>
	 {

	    typedef T* pointer;
	    //pointer tree_node;	
	    typedef typename CContainer::iterator it;
	    it parent;
		int level;
	  	    //pedef std::multimap<T*,T> CContainer;
	    CContainer* _tree;

	    protected:
	    
	    it getParent()
	    {
	       return parent;
	    }
	    
	    it findParent(T* par)
	    {
	       it s_node;
	       s_node=_tree->begin();
	       
	       while (&(s_node->second) != par)
	       {
				s_node++;
	       }
	       return s_node;
	    }

	    public:
	    tree_iterator(it node,CContainer *_mainTree)
	    {
	       parent=node;
	       _tree=_mainTree;
		   level = 0;
	    };
	
	
	    pointer getLink()
		{
		    return &(parent->second);
		}	
	    pointer getLinkParent()
		{
		    return parent->first;
		}	



	 
	    
	    const T& operator*() const
	    {
	       return parent->second;
	    }
	    //pointer operator*() const
	    //{
	    //   return &(parent->second);
	    //}


	    pointer operator->() const
	    {
	       return &(parent->second);
	    }

		int getLevel()
		{
			return level;
		}

	    
	    tree_iterator operator++(int)
	    {
	        it s_node;
			int sex;
	        int kind;
			T* par;
	       int i= _tree->count(&(parent->second));
	       switch (i)
	       {
			case 1:
				s_node = _tree->find(&(parent->second));
				parent = s_node;
				level++;
				break;

			case 2:
				s_node = _tree->find(&(parent->second));
				sex = s_node->second.getSex();
				switch(sex)
				{
				case 0: 
				    parent = s_node;
				    break;
				 case 1:
				    s_node++;
				    parent = s_node;

				    break;
				}	    
				level++;
				break;
		  case 0:
			bool r=false;

			while (!r)
			{
			   sex = parent->second.getSex();
				
			   switch (sex)
			   {
			      case 0:
					
					kind = _tree->count(parent->first);
					switch (kind)
					{
						case 1:
							//par = parent->first;						
							//if (par ==(NULL)) r=true;
							if (level == 0) r = true;
							else
							{
								level--;
								parent = findParent(parent->first);
					     
							}	     
						break;
						case 2:
							r =true;
							s_node = _tree->find(parent->first);
							
							sex = s_node->second.getSex();
							switch(sex)
							{
								case 0: 
									parent++;
									break;
								case 1:
									parent--;
									break;
							}	  

							break;
					}   
					break;
			      case 1:
					//par = parent->first;
					//if (par == 0) r=true;
					if (level == 0) r=true;
					else
					{   
						level--;
						parent = findParent(parent->first);
					}
					break;
			   }
	 	
			}   
			break;
	       }
       
	        return (*this);
	     }

	    
	 };
   
};

template <typename T>
std::ostream& operator<<(std::ostream& str,CTree<T> &mtree)
{
	try 
	{
		if (mtree.empty())
		{
			CTreeException noNode(0,"operator<<	",mtree.size(),9);
			throw noNode;
		}
		str << mtree.size()<<std::endl;
		//str << vid_sex << std::endl;
		typename CTree<T>::tree_iterator t = mtree.begin();
        str << t.getLinkParent() <<std::endl;
		str << t.getLink() <<std::endl;	
		str << *t;
		for (int i=1; i<mtree.size(); i++)
		{
			t++;
			str << t.getLinkParent() <<std::endl;
			str << t.getLink() <<std::endl;	
			str << *t;
		}
	}
	catch (CTreeException &err)
	{
		
		CSerialException s_err(1,"operator <<",err.getnameMess());
		throw s_err;
	}
	return str;
}

template <typename T>
std::istream& operator>>(std::istream& str,CTree<T> &mtree)
{
	try
	{
		int i;

		mtree.clear();
		str >> i;
		if (i <= 0)
		{
			CTreeException noNode(0,"operator<<	",i,9);
			throw noNode;
		}
		//str >> vid_sex;
		std::string NumP; 
		std::string NumN;
		str >> NumP;
		str >> NumN;
		CPerson pers;
		str >> pers;
		mtree.addRoot(pers);
		typedef std::multimap<string,T*> CTableNum;
		typename CTree<T>::tree_iterator t = mtree.begin();
		
		CTableNum table;
		table.insert(make_pair(NumN, t.getLink()));
		typename CTableNum::iterator table_link;
		for (int j=1; j<i; j++)
		{
			str >> NumP;
			str >> NumN;
			str >> pers;
			table_link = table.find(NumP);
			if (table_link == table.end())
				{
					CTreeException noNode(2,"operator<<	",i,9);
					throw noNode;
				}
			mtree.addNode(table_link->second, pers);
			t++;
			table.insert(make_pair(NumN, t.getLink()));
		}
	}
	catch (CTreeException &err)
	{
		
		CSerialException s_err(2,"operator <<",err.getnameMess());
		mtree.clear();
		throw s_err;
	}
	return str;
}

}


#endif
